/**
 * \file
 */
#include <stdint.h>

template<typename uint_t>
inline
uint_t div_ceil(uint_t dividend, uint_t divisor)
{

        uint_t quotient = dividend / divisor;
        uint_t remainder = dividend % divisor;
        if(remainder)
            return quotient + 1;
        else
            return quotient;
}

/**
 * The population count of an integer x is the number of one bits
 * in the value.
 * @return the population count of x
 */
inline
uint32_t
ones32(uint32_t x)
{
    /* 32-bit recursive reduction using SWAR...
     * but first step is mapping 2-bit values
     * into sum of 2 1-bit values in sneaky way
     */
    x -= ((x >> 1) & 0x55555555);
    x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
    x = (((x >> 4) + x) & 0x0f0f0f0f);
    x += (x >> 8);
    x += (x >> 16);
    return x & 0x0000003f;
}

/**
 * Given a natural number x, efficiently compute the floor of the base 2
 * logarithm of x.
 *
 * Since log(0) is undefined this implementation may return 0 or -1.
 */
inline
uint32_t
floor_log2(uint32_t x)
{
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    // If log(0) should be -1
    //return(ones32(x) - 1);
    // If log(0) should be zero:
    return(ones32(x >> 1));
}
